package algorithm;

/**
 * @author fangkun
 * @create 2022-05-20-9:55
 *
 * 34
 * 给定⼀个按照升序排列的整数数组 nums，和⼀个⽬标值 target，找出给定⽬标值在数组中的开始位置和结
 * 束位置。如果数组中不存在⽬标值 target，返回 [-1, -1]。
 */
public class FindpositioninSortedArray {

    public static void main(String[] args) {
        searchRange(new int[]{5,7,7,8,8,10},8);
    }

    public static int[] searchRange(int[] nums, int target) {
        return new int[]{left_bound(nums, target), right_bound(nums, target)};
    }

    static int left_bound(int[] nums, int target) {

        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]

        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    static int right_bound(int[] nums, int target) {

        int left = 0, right = nums.length - 1;

        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {

                left = mid + 1;

            } else if (nums[mid] > target) {

                right = mid - 1;

            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况，见下图
        if (right < 0 || nums[right] != target) {
            return -1;
        }

        return right;
    }
}
